import java.util.*;

public class TopKFrequentWords {
    public List<String> topKFrequent(String[] words, int k) {
        // 1.统计每个单词出现的频次
        Map<String, Integer> hash = new HashMap<>();
        for(String str : words) {
            hash.put(str, hash.getOrDefault(str, 0) + 1);
        }

        // 2.创建小根堆存前K个出现次数最多的单词
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>
                (
                        (a, b) ->
                        {
                            if(a.getValue().equals(b.getValue())) {  // 频次相同, 按字典序排大根堆
                                return b.getKey().compareTo(a.getKey());
                            }
                            return a.getValue() - b.getValue();
                        }
                );

        // 3.遍历哈希表里面的元素, 依次入堆
        // 用 Entry 这个结构一个一个的取出 hash 里面的键值对
        for(Map.Entry<String, Integer> entry : hash.entrySet()) {
            heap.offer(new Pair<>(entry.getKey(), entry.getValue()));
            if(heap.size() > k) {
                heap.poll();
            }
        }

        // 4.取出堆顶元素, 添加到数组中
        List<String> list = new ArrayList<>();
        while(!heap.isEmpty()) {
            list.add(heap.poll().getKey());
        }

        // 逆序数组
        Collections.reverse(list);
        return list;
    }
}
